package com.cuz.daileetcode.utils.unionsearchset;


import java.util.*;

/***
 * 并查集
 */
public class UnionSearchSet<T> {

    /***
     * 用于记录所有存在于并查集的元素
     * key 源用户的数据  value：包装一层的 Element 对象
     * @see Element 为什么包一层
     */
    private Map<T, Element<T>> allElementMemory;
    /***
     * 元素指向 代表元素的 map
     * key 元素
     * value 代表元素 此代表元素说明了key属于哪一个集合
     * 初始化时 所有元素本身就是代表元素
     */
    private Map<Element<T>, Element<T>> subPointToRepresent;
    /***
     * 并查集一个集合的大小
     * 哪个集合：key 是代表元素，此代表元素象征一个元素
     * 大小多少：value 所代表的指
     * 初始化时每个集合大小都是1
     */
    private Map<Element<T>, Integer> setSize;

    private UnionSearchSet() {
    }

    public static <T> UnionSearchSet<T> create(List<T> allDataList) {
        if (Objects.isNull(allDataList)) {
            throw new IllegalArgumentException("入参不为null");
        }
        //初始化
        UnionSearchSet<T> unionSearchSet = new UnionSearchSet<T>();
        unionSearchSet.allElementMemory = new HashMap<>(allDataList.size());
        unionSearchSet.subPointToRepresent = new HashMap<>(allDataList.size());
        unionSearchSet.setSize = new HashMap<>(allDataList.size());
        for (T dataLoopTemp : allDataList) {
            Element<T> element = Element.of(dataLoopTemp);
            //记录下元素对应的element
            unionSearchSet.allElementMemory.put(dataLoopTemp, element);
            //每一元素初始化时自己都是代表源
            unionSearchSet.subPointToRepresent.put(element, element);
            //每一个元素自己成一个集合 so size为1
            unionSearchSet.setSize.put(element, 1);
        }
        return unionSearchSet;
    }

    /***
     * 子节点找寻自己的代表节点
     * @param subElement 子节点
     * @return 代表节点，此节点可以看作根节点 象征了 subElement 属于哪个集合
     */
    private Element<T> findRepresentOf(Element<T> subElement) {
        List<Element<T>> alongWayElementMemory = new ArrayList<>();
        //当还不是代表节点
        while (subElement != subPointToRepresent.get(subElement)) {
            //记录下沿途的节点 何为沿途节点，把 代表节点想象成根节点
            //属于当前结合的节点 指向 代表节点
            //比如节点A是代表节点
            //B->C->A B和C就属于A代表的集合,B 和 C称为沿途节点
            alongWayElementMemory.add(subElement);
            //刷新
            subElement = subPointToRepresent.get(subElement);
        }
        // 让每一个沿途的节点指向代表节点，使其扁平化
        //B->C->A 转变成 B->A,C-A
        //这样下次进行查找时 时间复杂度将降低 这也是为什么并查集 查询是否同一个集合时间度O（1）的原因
        for (Element<T> alongWayElement : alongWayElementMemory) {
            subPointToRepresent.put(alongWayElement, subElement);
        }
        return subElement;
    }

    /***
     * 元素1 和元素 2 是否处于同一个集合
     * @param data1 元素1
     * @param data2 元素2
     * @return 是否同一个集合
     */
    public boolean bothInOneSetOrNot(T data1, T data2) {
        Element<T> element1 = allElementMemory.get(data1);
        Element<T> element2 = allElementMemory.get(data2);
        //我们要求这俩节点在初始化的时就加入了 并查集了
        if (Objects.nonNull(element1) && Objects.nonNull(element2)) {
            //找他们的代表集合 代表元素相同任务在同一个集合
            Element<T> representOf1 = findRepresentOf(element1);
            Element<T> representOf2 = findRepresentOf(element2);
            return Objects.equals(representOf1, representOf2);
        }
        return false;
    }

    /***
     * 合并 元素1 元素2 所在的集合
     * 注意不是合并元素1 和元素 2到一个集合
     * 而是合并他们所属于的集合为集合
     * @param data1 元素1
     * @param data2 元素2
     * @return 是否成功合并 ，
     * 如果两个元素存在任何一个初始化时没有加入并查集 那么返回false
     */
    public boolean unionSetOf(T data1, T data2) {
        Element<T> element1 = allElementMemory.get(data1);
        Element<T> element2 = allElementMemory.get(data2);
        //我们要求这俩节点在初始化的时就加入了 并查集了
        if (Objects.nonNull(element1) && Objects.nonNull(element2)) {
            Element<T> represent1 = findRepresentOf(element1);
            Element<T> represent2 = findRepresentOf(element2);
            Integer size1 = setSize.get(represent1);
            Integer size2 = setSize.get(represent2);
            Element<T> lessSizNode;
            Element<T> betterSizNode;
            //初始化较小的集合的代表节点 和较大的代表节点
            if (size1 < size2) {
                lessSizNode = represent1;
                betterSizNode = represent2;
            } else {
                lessSizNode = represent2;
                betterSizNode = represent1;
            }
            //然后较小集合的代表元素指向较大的较大集合的代表元素
            subPointToRepresent.put(lessSizNode, betterSizNode);
            //更新较大集合的大小
            setSize.put(betterSizNode, size1 + size2);
            //移除较小的代表，因为它已经不是代表元素了
            setSize.remove(lessSizNode);
        }
        return false;
    }
}
